//
//  RobChoice.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/8/5.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  198. 213. 337打家劫舍

import UIKit

/*
 打家劫舍问题
 
 198. 打家劫舍
 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

  
 示例 1：

 输入：[1,2,3,1]
 输出：4
 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
      偷窃到的最高金额 = 1 + 3 = 4 。
 示例 2：

 输入：[2,7,9,3,1]
 输出：12
 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 */

class RobChoice: NSObject {
    /*
     动态规划解法
     每个房间的现金用nums表示   eg:nums = [1,2,3,1]
     设 f[i]表示一共i个房间 按照如上规则进行偷窃能偷到的最多现金。
     f[0] = 0
     f[1] = nums[0]
     f[2] = max(nums[0],nums[1])
     
     从第三个房间开始，就要开始有考虑
     偷第三个房间意味着不能偷第二个房间，不偷第三个房间意味着刚刚已经偷过第二个房间，
     f[3] = max(f[1]+nums[2])
     
     那么可以得出动态转移方程
     f[i] = max(f[i-2]+nums[i-1] , f[i-1])

     然后便可求解
     
     */
    func rob(_ nums: [Int]) -> Int {
        
        guard nums.count != 0 else {
            return 0
        }
        guard nums.count != 1 else {
            return nums[0]
        }
        
        var dp = [Int].init(repeating: 0, count: nums.count+1)
        dp[1] = nums[0]
        dp[2] = max(nums[0], nums[1])
        
        for i in 3 ..< dp.count{
            dp[i] = max(dp[i-2]+nums[i-1], dp[i-1])
        }
        
        return dp.last!
    }
    //从上面的解法可以发现f[i] 只和前面两个数有关 因此可以用滚动数字思想优化空间复杂度
    func robRollArr(_ nums: [Int]) -> Int {
        guard nums.count != 0 else {
            return 0
        }
        guard nums.count != 1 else {
            return nums[0]
        }

        var a = nums[0]
        var b = max(nums[0], nums[1])
        
        for i in 2 ..< nums.count{
            let tmp = b
            b = max(a + nums[i], b)
            a = tmp
        }
        
        return b
    }
    
    
    
    
    /*
     问题延伸>>>>>>>>>>>>>>>>>>>>
     213. 打家劫舍 II
     
     你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，
     这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

     给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
     */
    
    //根据题意，我们可分成两种情况即偷第一个房间和不偷第一个房间 求出两者最大值。
    //即 [2 ... n] 个房间 和 [1 ... n-1] 个房间这两种情况
    func rob2(_ nums: [Int]) -> Int {
        guard nums.count != 0 else {
            return 0
        }
        guard nums.count != 1 else {
            return nums[0]
        }
        guard nums.count != 2 else {
            return max(nums[0], nums[1])
        }

        var a = nums[0]
        var b = max(nums[0], nums[1])
        
        for i in 2 ..< nums.count-1{
            let tmp = b
            b = max(a + nums[i], b)
            a = tmp
        }
        
        
        var a2 = nums[1]
        var b2 = max(nums[1], nums[2])
        
        for i in 3 ..< nums.count{
            let tmp = b2
            b2 = max(a2 + nums[i], b2)
            a2 = tmp
        }
        
        return max(b, b2)
    }
    
    
    
    
    
    
    
    /*
     问题延伸>>>>>>>>>>>>>>>>>>>>
     337. 打家劫舍 III
     在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

     计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

     示例 1:
     输入: [3,2,3,null,3,null,1]

          3
         / \
        2   3
         \   \
          3   1

     输出: 7
     解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

     示例 2:
     输入: [3,4,5,1,3,null,1]

          3
         / \
        4   5
       / \   \
      1   3   1

     输出: 9
     解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
     */
    
    /*
     解题思路
     每个节点都设置：[偷, 不偷]

     每一个节点的偷值都是：左侧子节点的不偷值 + 右侧子节点的不偷值 + 该节点的值
     每一个节点的不偷值都是： 左侧子节点的最大值 + 右侧子节点的最大值

     */
    func rob3(_ root: TreeNode?) -> Int {
        let rootStatus = self.dfs(root)             //a 是一个二维数组, 为root的[偷值, 不偷值]
        return max(rootStatus[0], rootStatus[1])    //返回两个值的最大值, 此值为小偷最终获得的总值
    }
    
    //参数为root节点, dfs方法输出一个二维数组：root节点的[偷值, 不偷值]
    func dfs(_ root: TreeNode?) -> [Int]{
        guard root != nil else {
            return [0,0]
        }
        let l = self.dfs(root?.left)        //left是一个二维数组, 为 root 左侧子节点的[偷值, 不偷值]
        let r = self.dfs(root?.right)       //right也是一个二维数组, 为root右侧子节点的[偷值, 不偷值]
        
        let selected = root!.val + l[1] + r[1]              //root 的偷值
        let noSelected = max(l[0], l[1]) + max(r[0], r[1])  // root 的不偷值
        
        return [selected,noSelected]        //输出小偷可获得的最大金额
    }
}
